import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.util.BitSet;

/**
 * BloomFilter
 * 
 * @author Neil Cutshaw
 * @version 1.0
 * Created 10/8/2006
 * Last Modified 10/9/2006
 * 
 * This class represents a Bloom Filter.  Along with traditional functionality, BloomFilter
 * can also write and read itself from a FileInputStream or FileOutputStream.
 */
public class BloomFilter {

	/** Number of hash functions to use.  Can support up to 10 */
	public static final int HASHES = 5;
	
	/** Debug value */
	public static final boolean DEBUG = false;
	
	/** Hash Function Library */
	public static GeneralHashFunctionLibrary lib = new GeneralHashFunctionLibrary();
	
	/** Data stucture to hold the bits */
	private BitSet bits;
	
	/** Size of this Bloom Filter */
	private int size;
	
	/**
	 * Standard Constructor
	 * @param input the size of the bloom filter.
	 */
	public BloomFilter(int input) {
		// Have to round the input to some multiple of 8.
		if (input % 8 == 0) { 
			size = input;
		} else {
			size = (input - (input % 8)) + 8;
		}		
		
		if (DEBUG) {
			System.out.println("The size of this bloom filter is " + size);			
		}		
		bits = new BitSet(size);		
		// We have to set the last bit to guarantee the resulting bitset really is the
		// size we say it is.
		bits.set(size-1);
	}
	
	/**
	 * Constructor to construct a bloom filter from file.
	 * @param stream FileInputStream the bit array comes from
	 * @param input The size of the bloom filter.
	 */
	public BloomFilter(FileInputStream stream, int input) {		
		//Have to round the input to some multiple of 8.
		if (input % 8 == 0) { 
			size = input;
		} else {
			size = (input - (input % 8)) + 8;
		}		
		
		// Number of bytes this bloom filter takes up.
		byte[] buf = new byte[size/8+1];
		
		if (DEBUG)
			System.out.println("Reading in bloom filter from file of size: " + buf.length);		
		
		try {			
				stream.read(buf);
				bits = fromByteArray(buf);
				bits.set(size);				
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
	}
	
	public void addWord(String word) {
		if (DEBUG)
			System.out.println("Adding word to bloom filter: " + word);
		
		bits.set((int) (lib.APHash(word) % size));
		if (DEBUG) 
			System.out.println("Setting bit: " + lib.APHash(word) % size);
				
		if (HASHES > 1) {			
			bits.set((int) (lib.BKDRHash(word) % size));
			if (DEBUG) 
				System.out.println("Setting bit: " + lib.BKDRHash(word) % size);
		}
		if (HASHES > 2) {			
			bits.set((int) (lib.DEKHash(word) % size));
			if (DEBUG) 
				System.out.println("Setting bit: " + lib.DEKHash(word) % size);
		}
		if (HASHES > 3) {			
			bits.set((int) (lib.SDBMHash(word) % size));
			if (DEBUG) 
				System.out.println("Setting bit: " + lib.SDBMHash(word) % size);
		}
		if (HASHES > 4) {			
			bits.set((int) (lib.BPHash(word) % size));		
			if (DEBUG) 
				System.out.println("Setting bit: " + lib.BPHash(word) % size);
		}				
		if (HASHES > 5) {			
			bits.set((int) (lib.RSHash(word) % size));		
			if (DEBUG) 
				System.out.println("Setting bit: " + lib.RSHash(word) % size);
		}
		if (HASHES > 6) {			
			bits.set((int) (lib.JSHash(word) % size));		
			if (DEBUG) 
				System.out.println("Setting bit: " + lib.JSHash(word) % size);
		}
		if (HASHES > 7) {			
			bits.set((int) (lib.PJWHash(word) % size));		
			if (DEBUG) 
				System.out.println("Setting bit: " + lib.PJWHash(word) % size);
		}
		if (HASHES > 8) {			
			bits.set((int) (lib.ELFHash(word) % size));		
			if (DEBUG) 
				System.out.println("Setting bit: " + lib.ELFHash(word) % size);
		}
		if (HASHES > 9) {			
			bits.set((int) (lib.DJBHash(word) % size));		
			if (DEBUG) 
				System.out.println("Setting bit: " + lib.DJBHash(word) % size);
		}
		
		
		
		
	}
	
	public boolean wordExists(String word) {		
		if (!bits.get((int) (lib.APHash(word) % size))) {
			return false;
		}
		if (HASHES > 1) {	
			if (!bits.get((int) (lib.BKDRHash(word) % size))) {
				return false;
			}
		}
		if (HASHES > 2) {	
			if (!bits.get((int) (lib.DEKHash(word) % size))) {
				return false;
			}
		}
		if (HASHES > 3) {	
			if (!bits.get((int) (lib.SDBMHash(word) % size))) {
				return false;
			}
		}
		if (HASHES > 4) {	
			if (!bits.get((int) (lib.BPHash(word) % size))) {
				return false;
			}
		}
		if (HASHES > 5) {	
			if (!bits.get((int) (lib.RSHash(word) % size))) {
				return false;
			}
		}
		if (HASHES > 6) {	
			if (!bits.get((int) (lib.JSHash(word) % size))) {
				return false;
			}
		}
		if (HASHES > 7) {	
			if (!bits.get((int) (lib.PJWHash(word) % size))) {
				return false;
			}
		}
		if (HASHES > 8) {	
			if (!bits.get((int) (lib.ELFHash(word) % size))) {
				return false;
			}
		}
		if (HASHES > 9) {	
			if (!bits.get((int) (lib.DJBHash(word) % size))) {
				return false;
			}
		}
				
		return true;					
	}
	
	public void writeBloomToFile(FileOutputStream stream) {
		
		byte[] buf = toByteArray(bits);
		if (DEBUG) 
			System.out.println("Writing to file bytes: " + buf.length);
		
		try {										
				stream.write(buf);
				stream.flush();									
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
			
		
	
	}
	
    // Returns a bitset containing the values in bytes.
    // The byte-ordering of bytes must be big-endian which means the most significant bit is in element 0.
    private BitSet fromByteArray(byte[] bytes) {
        BitSet bits = new BitSet();
        for (int i=0; i<bytes.length*8; i++) {
            if ((bytes[bytes.length-i/8-1]&(1<<(i%8))) > 0) {
                bits.set(i);
            }
        }
        return bits;
    }
    
    // Returns a byte array of at least length 1.
    // The most significant bit in the result is guaranteed not to be a 1
    // (since BitSet does not support sign extension).
    // The byte-ordering of the result is big-endian which means the most significant bit is in element 0.
    // The bit at index 0 of the bit set is assumed to be the least significant bit.
    private byte[] toByteArray(BitSet bits) {
        byte[] bytes = new byte[bits.length()/8+1];
        for (int i=0; i<bits.length(); i++) {
            if (bits.get(i)) {
                bytes[bytes.length-i/8-1] |= 1<<(i%8);
            }
        }                 
        return bytes;
    }
}

